#include <iostream>
#include <vector>
using namespace std;

// return the index right less than target
int FindPoint(int A[], int n, float target){
    if(n==0 || A[0] > target){
        return -1;
    }
    if(target > A[n-1]){
        return n-1;
    }
    int left = 0;
    int right = n;
    while(left < right-1){
        int mid = (left+right)/2;
        if(A[mid] < target){
            left = mid;
        }
        else{
            right = mid;
        }
    }
    return left;
}

int FindMargin(int A[], int n, int target, int mode){
    int left = 0;
    int right = n;

    while(left < right -1){
        int mid = (left + right)/2;
        if(A[mid] < target){
            left = mid+1;
        }
        else if(A[mid] > target){
            right = mid;
        }
        else{
            if(mode==0){
                if(mid==0){
                    return 0;
                }
                else if(A[mid-1] < target){
                    return mid;
                }
                else{
                    right = mid;
                }
            }
            else{
                if(mid==n-1){
                    return n-1;
                }
                else if(A[mid+1] > target){
                    return mid;
                }
                else{
                    left = mid;
                }
            }
        }
    }
    if(A[left] == target){
        return left;
    }
    else{
        return -1;
    }
}


vector<int> searchRange(int A[], int n, int target) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    vector<int> res;
    if(n==0){
        res.push_back(-1);
        res.push_back(-1);
        return res;
    }

//     res.push_back(FindMargin(A, n, target, 0));
//     res.push_back(FindMargin(A, n, target, 1));
    
    int left = FindPoint(A, n, target-0.01f);
    if(left+1 < n && A[left+1] == target){
        res.push_back(left+1);
    }
    else{
        res.push_back(-1);
    }
    int right = FindPoint(A, n, target+0.01f);
    if(right >=0 && right < n && A[right] == target){
        res.push_back(right);
    }
    else{
        res.push_back(-1);
    }

    return res;
}

int main(){
    int A[3] = {1,2,2};
    searchRange(A, 3, 2);

    return 0;
}